LeetCode Solution - Next Permutation

https://leetcode.com/problems/next-permutation/

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

The test case given in the question is not enough for us to understand this question. So I will use another example to explain this question.

Let 1,2,3,4,5 is the input array nums. It is easy to write down its next permutation which is 1,2,3,5,4. What about 1,2,3,5,4‘s next permutation? It’s 1,2,4,3,5. And why?

The reason is that we have listed all possible permutations that index[nums.length - 2] greater than index[nums.length - 1], we should think about condition that the last three numbers contain a non-lexicographically permutation of numbers. The smallest one is that index[nums.length - 3] is the second smallest number in the last three numbers, and numbers after that should be in an ascending order. Why numbers should be in an ascending order? Because the question defines that this is a smallest condition.

The following should be 1,2,4,5,3, 1,2,5,3,4, 1,2,5,4,3, 1,3,2,4,5, 1,3,2,5,4, 1,3,4,2,5, 1,3,4,5,2, 1,3,5,2,4, 1,3,5,4,2, 1,4,2,3,5, 1,4,2,5,3, 1,4,3,2,5, 1,4,3,5,2, 1,4,5,2,3, 1,4,5,3,2, etc.

public class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return;
        }
        
        int index = -1;
        // find the position where the value is smaller than its follower
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                index = i - 1;
                break;
            }
        }
        // if index equals -1, this means the array is in an non-ascending,
        // order, it doesn't have next permutation, or it's next permutation
        // is the lowest possible order (ie, sorted in ascending order).  
        if (index == -1) {
            reverse(nums, 0, nums.length - 1);
            return;
        }
        // find the position where the value is greater than the value stored
        // in nums[index]. Remember that index is the position where we need to
        // make some changes.
        for (int i = nums.length - 1; i > index; i--) {
            // exchange 
            // e.g. for 5,4,7,5,3,2; index = 1, i = 3
            // The result will be 5,5,7,4,3,2
            // Numbers after i = 3 (nums[i] = 5) is in an non-ascending order,
            // which means it's the greatest possible order. So the next   
            // permutation should start with the number smallest greater than 5. 
            // And the number after index will also in an non-ascending order.
            if(nums[i] > nums[index]){
                int temp = nums[i];
                nums[i] = nums[index];
                nums[index] = temp;
                break;
            }
        }
        // once we get 5,5,7,4,3,2 from 5,4,7,5,3,2, we should reverse the order 
        // from 7 to 2 to get the lowest possible order.
        reverse(nums, index + 1, nums.length - 1);
        return;
    }
    private void reverse(int[] nums, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }
    }
}

Another version of solution which helps me a lot to understand this question.

https://leetcode.com/discuss/85045/20-line-1ms-in-place-java-code-with-expalantion

1. scan from right to left, find first pair where a[i] > a[i-1]. note that a[i:] is non-ascending.
2. scan from right to left again, find first element a[j] where a[j] > a[i-1]. since a[i:] is non-ascending, a[j] is the smallest number that > a[i-1].
3. swap a[i-1] with a[j]. note that after swap, a[i:] remains non-ascending.
4. reverse a[i:] so that a[i:] becomes non-descending.

public class Solution {
    public void nextPermutation(int[] nums) {
        int p = nums.length-1;
        while (p>0 && nums[p]<=nums[p-1]) { --p; }
        if (p == 0) {  // case like [3,2,1]
            reverse(nums, 0, nums.length-1);
            return;
        }
        int q = nums.length-1;
        while (nums[q]<=nums[p-1]) { --q; }
        int temp = nums[p-1]; nums[p-1] = nums[q]; nums[q] = temp;
        reverse(nums, p, nums.length-1);
    }

    private void reverse(int[] a, int from, int to) {
        for (; from < to; ++from, --to) {
            int temp = a[from];
            a[from] = a[to];
            a[to] = temp;
        }
    }
}